#ifndef MESH_H
#define MESH_H
#include <map>
#if defined(_MSC_VER)
	#include <hash_map>
#elif defined(__GNUC__)
	#include <ext/hash_map>
#endif

#include <fstream>
#include <iostream>
#include <string>

class HalfEdge ;
class Edge;
class Face;
class Vertex; 

class HalfEdge 
{
public:
	HalfEdge * next, * prev, * flip;
	Face * face;
	Vertex * from_v ;
	Edge * edge; 
};

class Face 
{
	
public:
Face (): resolution(4)
{
}
public: 
	HalfEdge * he;
	unsigned resolution; 
	color_RGB color; 
} ;


class Vertex
{
public:
	Vertex () {}
	class VVIter 
	{
	public:
		VVIter (Vertex * v)
		{
			he = v->he; 
		};
		VVIter (HalfEdge * edge)
		{
			he = edge; 
		}
		VVIter & operator ++()
		{
			this->he = he->flip->next ;
			return (*this) ;
		}
		Vertex * operator*()
		{
			return (this->he->flip->from_v);
		}
		bool operator ==(const VVIter & other)
		{
			return(he == other.he);
		}

		bool operator!=(const VVIter & other)
		{
			return(he != other.he);
		}
	private :
		HalfEdge * he;  
	};
public:
	VVIter vvbegin ()
	{
		return VVIter (this) ;
	}
	VVIter vvend ()
	{
		return VVIter (this);
	}
public: 
	Point point; 
	HalfEdge * he; 
	unsigned idx ;

	unsigned num_neigh ;
	Point sum_neigh ;
	float qua_sum_neigh ; 

};
class Edge 
{
public :
	HalfEdge * he ; 
	friend std::ostream & operator << (std::ostream & ostr, Edge * e)
	{
		ostr <<'('<<e->he->from_v->idx<<','; 
		ostr <<e->he->flip->from_v->idx<<')';
		return ostr;
	}
	float cost; 
};

typedef std::pair<int, int> HashKey;
typedef HashKey HalfEdgeHashKey ;
typedef HashKey EdgeHashKey; 

class FaceHashKey
{
public:
	FaceHashKey(unsigned a, unsigned b, unsigned c)
	{
		idx1 = a; idx2 = b; idx3 = c;
	}
public:
	unsigned idx1, idx2, idx3 ;
};


#if defined(_MSC_VER)


template<>
struct stdext::hash_compare<HashKey > {
    // the mean number of elements per bucket
    static const size_t bucket_size = 4;
    // the minimum number of buckets
    static const size_t min_buckets = 65535*16;
    // hash function
    size_t operator()(const HashKey & key) const {
        return (key.first * key.second);
    }
    // compare function
    bool operator()(const HashKey & lhs, const HashKey & rhs) const {
        return lhs < rhs;
    }
};

template<>
struct stdext::hash_compare<FaceHashKey > {
    // the mean number of elements per bucket
    static const size_t bucket_size = 4;
    // the minimum number of buckets
    static const size_t min_buckets = 65535*2;
    // hash function
    size_t operator()(const FaceHashKey & key) const {
		return key.idx1 * key.idx2 + key.idx3 ;
    }
    // compare function
    bool operator()(const FaceHashKey & lhs, const FaceHashKey & rhs) const {
		return (lhs.idx1 < rhs.idx1 || 
			(lhs.idx1 == rhs.idx1 && lhs.idx2 < rhs.idx2) ||
			(lhs.idx1 == rhs.idx1 && lhs.idx2 == rhs.idx2 && lhs.idx3 < rhs.idx3)) ;
    }
};


#elif defined(__GNUC__)
	struct EdgeHashOperator {
		size_t operator()(const EdgeHashKey & key) const {
        return (key.first * key.second);
    }
	};
	struct EdgeHashEqual {
		bool operator()(const EdgeHashKey & lhs, const EdgeHashKey & rhs) const {
			return lhs == rhs;
    }
	};

	struct FaceHashOperator {
		size_t operator()(const FaceHashKey & key) const {
        return (key.idx1 * key.idx2 + key.idx3);
    }
	};
	struct FaceHashEqual {
		bool operator()(const FaceHashKey & lhs, const FaceHashKey & rhs) const {
			return ( lhs.idx1 == lhs.idx1 
				  && lhs.idx2 == lhs.idx2 
				  && lhs.idx3 == lhs.idx3 );
    }
};

#endif
inline HalfEdgeHashKey halfEdgeHashKey (HalfEdge * he)
{
	unsigned id1 = he->from_v->idx ;
	unsigned id2 = he->next->from_v->idx; 
	return std::make_pair (id1, id2);
}
inline EdgeHashKey edgeHashKey (unsigned id1, unsigned id2)
{
	return (id1 < id2 ? std::make_pair(id1, id2) : std::make_pair(id2, id1)) ;
}
inline EdgeHashKey edgeHashKey(Edge * edge)
{
	if (edge == NULL) 
	{
		std::cout<<"INVALID EDGE"<<std::endl;
	}
	unsigned id1 = edge->he->from_v->idx;
	unsigned id2 = edge->he->next->from_v->idx ;
	return edgeHashKey(id1, id2);
}
inline FaceHashKey faceHashKey (unsigned id1, unsigned id2, unsigned id3)
{
	if (id1 < id2  && id1 < id3) return FaceHashKey(id1, id2, id3 );
	if (id2 < id1  && id2 < id3) return FaceHashKey(id2, id3, id1 );
	//if (id3 < id1  && id3 < id2) 
	return FaceHashKey(id3, id1, id2 );
	
}

inline FaceHashKey faceHashKey (Face * face)
{
	unsigned id1 = face->he->from_v->idx; 
	unsigned id2 = face->he->next->from_v->idx ;
	unsigned id3 = face->he->next->next->from_v->idx ;

	return faceHashKey (id1, id2, id3 );
}
inline void adjust_vertex (Vertex * v1, Vertex * v2)
{
	//std::vector <Vertex * > vertices; 
	v1->point = Point(v1->sum_neigh + v2->sum_neigh) / float(v1->num_neigh + v2->num_neigh); 
	v1->num_neigh +=  v2->num_neigh;
	v1->qua_sum_neigh += v2->qua_sum_neigh;
	v1->sum_neigh = v1->sum_neigh + v2->sum_neigh ;
}

inline bool is_edge_safe (Edge * edge)
{
	Vertex * v1 = edge->he->from_v ;
	Vertex * v2 = edge->he->next->from_v; 
	unsigned count = 0;
	Vertex::VVIter iter1 = v1->vvbegin ();
	Vertex::VVIter end1 = v1->vvend();
	do 
	{
		Vertex::VVIter iter2 = v2->vvbegin ();
		Vertex::VVIter end2 = v2->vvend();
		do
		{
			//std::cout<<"TEST"<<std::endl;
			if ( (*iter1)->idx == (*iter2)->idx ) count ++; 
			//std::cout<<(*iter2)->idx<<' ';
			++iter2;
		}while (iter2 != end2);
		++iter1;
	}while (iter1 != end1);
	return (2 == count);
}



#if defined(_MSC_VER)
	typedef stdext::hash_map <unsigned, Vertex * > VERTEX_CONTAINER ;
	typedef stdext::hash_map <EdgeHashKey, Edge * > EDGE_CONTAINER ;
	typedef stdext::hash_map <FaceHashKey, Face * > FACE_CONTAINER ;
	typedef stdext::hash_map <HashKey, HalfEdge * > HALFEDGE_CONTAINER ;
	
#elif defined(__GNUC__)
	typedef __gnu_cxx::hash_map <unsigned, Vertex * > VERTEX_CONTAINER ;
	typedef __gnu_cxx::hash_map <EdgeHashKey, Edge * , EdgeHashOperator, EdgeHashEqual> EDGE_CONTAINER ;
	typedef __gnu_cxx::hash_map <FaceHashKey, Face * , FaceHashOperator, FaceHashEqual> FACE_CONTAINER ;
	typedef __gnu_cxx::hash_map <HashKey, HalfEdge * , EdgeHashOperator, EdgeHashEqual> HALFEDGE_CONTAINER ;

#endif

	typedef VERTEX_CONTAINER::iterator VERTEX_ITERATOR ;
	typedef EDGE_CONTAINER::iterator EDGE_ITERATOR ;
	typedef FACE_CONTAINER::iterator FACE_ITERATOR ;
	typedef HALFEDGE_CONTAINER::iterator HALFEDGE_ITERATOR ;

class Mesh 
{
public: 
	friend std::istream & operator >> (std::istream & istr, Mesh & mesh)
	{
		std::string data; 
		Vertex * v; 
		unsigned count = 0; 
		while (istr >> data)
		{
			switch (data[0])
			{
			case 'v' :
				float x, y, z;
				istr >> x >> y >> z ;
				v = new Vertex;
				v->point.x = x*float(0.8) ; v->point.y = y * float(0.8); v->point.z = z*float(0.8);
				v->he = NULL; 
				v->idx = count ;
				mesh.vertices[count]=v;
				count ++ ;
				getline (istr, data);
				break;
			case 'f' :
				unsigned id1, id2, id3;
				istr >> id1 >> id2 >>id3 ;
				mesh.construct(id1-1, id2-1, id3-1);
				getline (istr, data );
				break;
			default :
				getline (istr, data);
			}
		}
		return istr;
	}
	~Mesh()
	{
		for (VERTEX_ITERATOR it = vertices.begin();
			it != vertices.end(); ++it)
		{
			if (it->second) delete (it->second);
			it->second = NULL; 			
		}
		std::cerr<<"Remove vertices"<<std::endl;

		for (FACE_ITERATOR it = faces.begin();
			it != faces.end(); ++it)
		{
			if (it->second) delete (it->second);
			it->second = NULL; 			
		}
		std::cerr<<"Remove faces"<<std::endl;
		
		for (EDGE_ITERATOR it = edges.begin(); 
			it !=edges.end(); ++it)
		{
			if (it->second) delete it->second; 
			it->second = NULL; 
		}
		std::cerr<<"Remove edges"<<std::endl;
		for (HALFEDGE_ITERATOR it = hash_he.begin(); 
			it != hash_he.end(); ++it)
		{
			if (it->second) delete it->second; 
			it->second = NULL; 
		}
		std::cerr<<"Remove Halfedges"<<std::endl;
	}


	void evaluate_edge_cost (Edge * edge)
	{
			Vertex * v1 = edge->he->from_v ;
			Vertex * v2 = edge->he->next->from_v ;

			Point p =  (v1->sum_neigh + v2->sum_neigh) / float(v1->num_neigh + v2->num_neigh) ;
			/*
			edge->cost = (v1->num_neigh + v2->num_neigh)*(p*p) - 
				p *(((v1->sum_neigh + v2->sum_neigh)) * 2.0) 
				+ v1->qua_sum_neigh + v2->qua_sum_neigh;
			*/
	}
	void evaluate_edge_around_vertex(Vertex * v)
	{
		HalfEdge * iter = v->he; 
		HalfEdge * end = iter;
		do
		{
			evaluate_edge_cost(iter->edge);
			iter = iter->flip->next ;
		} while(iter != end);
	}
	void prepare_simp_data()
	{
		for (VERTEX_ITERATOR v_iter = vertices.begin(); 
			v_iter != vertices.end(); ++v_iter)
		{
			unsigned count = 0;
			Point p(0.0, 0.0, 0.0);
			float sum = 0.0;
			Vertex::VVIter iter = (v_iter)->second->vvbegin();
			Vertex::VVIter end = (v_iter)->second->vvend();
			
			do 
			{
				++iter;
				++count;
				p = p + (*iter)->point; 
				sum += ((*iter)->point) * ((*iter)->point);
			} while (iter != end) ;
			v_iter->second->num_neigh = count;
			v_iter->second->sum_neigh = p; 
			v_iter->second->qua_sum_neigh = sum; 
		}
		for (EDGE_ITERATOR iter = edges.begin(); 
			iter != edges.end(); ++iter)
		{
			evaluate_edge_cost(iter->second);
		}
	}

private:

	void construct (const unsigned id1, const unsigned id2, const unsigned id3)
	{
		Face * face = new Face; 
		HalfEdge * he12 = new HalfEdge ;
		HalfEdge * he23 = new HalfEdge ;
		HalfEdge * he31 = new HalfEdge ;
		he12->prev = he31 ; he12->next = he23; he12->face = face; he12->from_v = vertices[id1] ;
		he23->prev = he12 ; he23->next = he31; he23->face = face; he23->from_v = vertices[id2] ;
		he31->prev = he23 ; he31->next = he12; he31->face = face; he31->from_v = vertices[id3] ;

		hash_he[HashKey(id1 , id2)] = he12;
		hash_he[HashKey(id2 , id3)] = he23;
		hash_he[HashKey(id3 , id1)] = he31;
		
		vertices[id1]->he = he12; 
		vertices[id2]->he = he23; 
		vertices[id3]->he = he31; 

		face->he =  he12 ;
		this->v_faces.push_back(face);

		faces[faceHashKey(id1, id2, id3)] = face;

		//Update the flips and Edges; 
		HALFEDGE_ITERATOR iter ;
		iter = hash_he.find(HashKey(id2, id1)) ;
		if (hash_he.end() == iter)
		{
			he12->flip = NULL;
			Edge * edge = new Edge;
			edge->he = he12 ;
			he12->edge = edge;
			if (id1 < id2) edges[HashKey(id1, id2)] = edge;
			else edges[HashKey(id2, id1)] = edge;
		}
		else
		{
			he12->flip = (*iter).second;
			(*iter).second->flip = he12 ;
			he12->edge = (*iter).second->edge ;
		}
		iter = hash_he.find(HashKey(id3, id2)) ;
		if (hash_he.end() == iter)
		{
			he23->flip = NULL;
			Edge * edge = new Edge;
			edge->he = he23 ;
			he23->edge = edge;
			if (id2 < id3) edges[HashKey(id2, id3)] = edge;
			else edges[HashKey(id3, id2)] = edge;
		}
		else
		{
			he23->flip = (*iter).second;
			(*iter).second->flip = he23 ;
			he23->edge = (*iter).second->edge ;
		}
		iter = hash_he.find(HashKey(id1, id3)) ;
		if (hash_he.end() == iter)
		{
			he31->flip = NULL;
			Edge * edge = new Edge;
			edge->he = he31 ;
			he31->edge = edge;
			if (id3 < id1) edges[HashKey(id3, id1)] = edge;
			else edges[HashKey(id1, id3)] = edge;
		}
		else
		{
			he31->flip = (*iter).second;
			(*iter).second->flip = he31 ;
			he31->edge = (*iter).second->edge ;
		}
	}
public:
	void print_halfedges ()
	{
		std::cout<<"HALF EDGE SIZE :"<<edges.size()*2<<std::endl;
		for (EDGE_ITERATOR iter = edges.begin(); 
			iter != edges.end(); ++iter )
		{
			HalfEdge * he1 = iter->second->he ;
			HalfEdge * he2 = iter->second->he->flip; 
			if (he1->next->next->next != he1) std::cout<<"Invalid Halfedge"<<std::endl;
			if (he2->next->next->next != he2) std::cout<<"Invalid Halfedge"<<std::endl;
			std::cout<<'['<<he1->from_v->idx<<','<<he1->next->from_v->idx<<']'<<std::endl;
			std::cout<<'['<<he2->from_v->idx<<','<<he2->next->from_v->idx<<']'<<std::endl;
		}
	}
	void print_vertex_neighbor(Vertex * v)
	{
		std::cout<<std::endl<<"VERTEX NEIGHBOR : "<<v->idx<<std::endl;
		HalfEdge * iter = v->he; 
		HalfEdge * end = iter; 
		do
		{
			std::cout<<'['<<iter->from_v->idx <<' '<<iter->next->from_v->idx <<' '<<iter->next->next->from_v->idx <<']'<<std::endl;
			iter = iter->flip->next ;
		}while (iter != end);
		
	}
	void print_edges ()
	{
		std::cout<<"EDGE SIZE :"<<edges.size()<<std::endl;
		for (EDGE_ITERATOR iter = edges.begin(); 
			iter != edges.end(); ++iter )
		{
			
			std::cout<<'['<<iter->first.first<<','<<iter->first.second<<']'<<iter->second; 
			if (iter->first != edgeHashKey(iter->second->he->from_v->idx, iter->second->he->next->from_v->idx ))
			{
				std::cout<<" INVALID EDGE--";
				std::cout<<'['<<iter->first.first<<','<<iter->first.second<<']'<<
					iter->second->he->from_v->idx<<','<<iter->second->he->next->from_v->idx <<std::endl;
				exit(0);
			}
			std::cout<<std::endl;
		}
	}
	void print_vertex ()
	{
		for (VERTEX_ITERATOR iter = vertices.begin ();
			iter != vertices.end(); ++iter )
		{
			std::cout<<iter->second->idx << ": ("<< iter->second->num_neigh<<')';

			Vertex::VVIter iter_in = iter->second->vvbegin();
			Vertex::VVIter end = iter->second->vvend();
			do 
			{
				std::cout<<(*iter_in)->idx<<' ';
				++iter_in;
			} while (iter_in != end) ;
			std::cout<<std::endl;
			
		}
	}
	void prepare_color()
	{
		for (std::vector<Face *>::iterator iter = v_faces.begin(); iter!= v_faces.end(); ++iter)
		{
			color_RGB color (randreal(), randreal(), randreal());
			(*iter)->color = color; 
		}
	}
	bool is_valid_mesh()
	{
		for (EDGE_ITERATOR iter = edges.begin(); 
			iter != edges.end(); ++iter )
		{
			HalfEdge * he1 = iter->second->he ;
			HalfEdge * he2 = iter->second->he->flip; 
			if (he1->next->next->next != he1)
			{
				std::cout<<"INVALID EDGE [CIRCLE1]:";
				return false;
			}
			if (he2->next->next->next != he2)
			{
				std::cout<<"INVALID EDGE [CIRCLE2]:";
				return false;
			}

			if (he1->next->from_v != he1->flip->from_v )
			{
				std::cout<<"\nINVALID EDGE [NEXT<->FLIP]1:"<<std::endl;
				print_vertex_neighbor(he1->from_v);
				print_vertex_neighbor(he1->next->from_v);
				print_vertex_neighbor(he1->flip->from_v);
				std::cout<<"NEXT "<<he1->next->from_v->idx<<' '<<he1->next->next->from_v->idx
					<<' '<<he1->next->next->next->from_v->idx<<std::endl;
				std::cout<<"FLIP "<<he1->flip->from_v->idx<<std::endl;
				return false;
			}
			if (he2->next->from_v != he2->flip->from_v )
			{
				std::cout<<"\nINVALID EDGE [NEXT<->FLIP]2:";
				print_vertex_neighbor(he2->from_v);
				print_vertex_neighbor(he2->next->from_v);
				print_vertex_neighbor(he2->flip->from_v);
				return false;
			}
			if (iter->first != edgeHashKey(iter->second->he->from_v->idx, iter->second->he->next->from_v->idx ))
			{
				std::cout<<std::endl;
				std::cout<<"INVALID EDGE [NEXT]:";
				std::cout<<'['<<iter->first.first<<','<<iter->first.second<<']'<<
					iter->second->he->from_v->idx<<','<<iter->second->he->next->from_v->idx <<std::endl;
				return false;
			}
			if (iter->first != edgeHashKey(iter->second->he->from_v->idx, iter->second->he->flip->from_v->idx ))
			{
				std::cout<<std::endl;
				std::cout<<" INVALID EDGE [FLIP]:";
				std::cout<<'['<<iter->first.first<<','<<iter->first.second<<']'<<
					iter->second->he->from_v->idx<<','<<iter->second->he->flip->from_v->idx <<std::endl;
				return false;
			}
		}
		return true;
	}
public:
	
	VERTEX_CONTAINER vertices;
	EDGE_CONTAINER edges; 
	FACE_CONTAINER  faces; 
	std::vector<Face * > v_faces;
	HALFEDGE_CONTAINER hash_he; 

};

#endif
